// https://www.lintcode.com/problem/perfect-string/

public class Solution {
    /**
     * @param s: string need to be transformed
     * @param k: minimum char can be transformed in one operation
     * @return: minimum times to transform all char into '1'
     */
    public int perfectString(String s, int k) {
        // Write your code here
        int ret = 0, cz = k;
        for (int i = 0; i < s.length(); ++i) {
            Character c = s.charAt(i);
            if (c == '0') {
                if (cz == k) {
                    ++ret; // 遇到0就替换，后面连着的0尽可能多的一起替换。
                }
                --cz;
            } else {
                cz = k; // 重置
            }
            if (cz == 0) { // 最多替换k个0
                cz = k;
            }
        }
        return ret;
    }
}